#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
const int maxn = 1e6 + 10;
const int MOD = 1e9+7;
ll ans[30][30], dist[30];
bool mark[30];
vector<pair<int, int>> vec[30];
void dijkstra(int st){
set<pair<int, int>> s;
for(int i = 0; i < 27; i++){
dist[i] = (i == st? 0: 1000000000);
mark[i] = (i == st? 1: 0);
s.insert({dist[i], i});
}
while(s.size()){
pii cur = *s.begin();
s.erase(cur);
int v = cur.S;
for(auto i : vec[v]){
ll u = i.F, w = i.S;
mark[u] = 1;
if(dist[u] > dist[v] + w){
s.erase({dist[u], u});
s.insert({dist[u] = dist[v] + w, u});
}
}
}
for(int i = 0; i < 27; i++){
if(mark[i]) ans[st][i] = dist[i];
else ans[st][i] = -1;
}
}
void solve(){
string s, s1;
int n;
cin>> s>> s1>> n;
if(s.size() != s1.size()){
cout<< -1;
return;
}
for(int i = 0; i < n; i++){
char x, y; int w;
cin>> x>> y>> w;
vec[x - 'a'].pb({y - 'a', w});
}
for(int i = 0; i < 27; i++) dijkstra(i);
vector <int> vec;
int anss = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == s1[i]){
vec.pb(s[i] - 'a');
continue;
}
int idk = -1;
int idk1 = 100000000;
for(int j = 0; j < 27; j++){
if(ans[s[i] - 'a'][j] == -1 || ans[s1[i] - 'a'][j] == -1){
continue;
}
if(idk1 > ans[s[i] - 'a'][j] + ans[s1[i] - 'a'][j]){
idk = j;
//cout<< (ans[s[i] - 'a'][j] + ans[s1[i] - 'a'][j] )<< " " << j << endl;
idk1 = ans[s[i] - 'a'][j] + ans[s1[i] - 'a'][j];
}
}
if(idk == -1){
cout<< -1;
return;
}
vec.pb(idk);
anss += idk1;
}
cout<< anss << endl;;
for(int i = 0; i < vec.size(); i++){
cout<< ((char)(vec[i] + 'a')) ;
}
}
int main(){
fast_io
solve();
return 0;
}
162. Find Peak Element | 1529A - Eshag Loves Big Arrays |
19. Remove Nth Node From End of List | 925. Long Pressed Name |
1051. Height Checker | 695. Max Area of Island |
402. Remove K Digits | 97. Interleaving String |
543. Diameter of Binary Tree | 124. Binary Tree Maximum Path Sum |
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts | 501A - Contest |
160A- Twins | 752. Open the Lock |
1535A - Fair Playoff | 1538F - Interesting Function |
1920. Build Array from Permutation | 494. Target Sum |
797. All Paths From Source to Target | 1547B - Alphabetical Strings |
1550A - Find The Array | 118B - Present from Lena |
27A - Next Test | 785. Is Graph Bipartite |
90. Subsets II | 1560A - Dislike of Threes |
36. Valid Sudoku | 557. Reverse Words in a String III |
566. Reshape the Matrix | 167. Two Sum II - Input array is sorted |